import java.util.Random;

/**
 * @author LKQ
 * @date 2022/3/5 10:13
 * @description
 */
public class Solution {
    public static void main(String[] args) {
        Object[] data = {1, 2, 5, 6, 7, 9 , 3, 2, 1, 8};
        Solution solution = new Solution();
        solution.poolSelect(data, 4);
    }

    /**
     *
     * @param dataSource 未知的数据流
     * @param k 等概率取k个样本
     * @return 获取的样本
     */
    public Object[] poolSelect(Object[] dataSource, int k) {
        Object[] ans = new Object[k];
        Random random = new Random();
        for (int i = 0; i < dataSource.length; i++) {
            if (i < k) {
                // 前 k 个样本，以概率 P = 1选择
                ans[i] = dataSource[i];
            }else {
                // 随机获得一个在[0,i]之间的随机数
                int d = random.nextInt(i + 1);
                // 如果随机数落在[0,k-1]之间
                if(d < k) {
                    // 选中的概率为 k / i *  1 / k = 1 / i，确保等概率选择。
                    ans[d] = dataSource[i];
                }
            }

        }
        return ans;
    }
}
